package com.universe.arithmetic.baseSort;

import java.util.Arrays;

/**
 * @Author：chenhuan
 * @Description： 插入排序
 * @Theory： 插入排序始终在列表的较低位置维护一个排序的子列表，遇到新的项将它插入到原来的子列表，
 * 使得排序的子列表称为一个较大的项
 * 平均时间复杂度 O（n^2） 空间复杂度 O（1） 稳定排序
 * @Date： 17:52 2019/6/6
 */
public class InsertionSort {

    public static void insertSort(int... array) {
        for (int i = 1; i <= array.length - 1; i++) {
            int insertIndex = i - 1;
            int insertValue = array[i];
            while (insertIndex >= 0 && array[insertIndex] > insertValue) {
                array[insertIndex + 1] = array[insertIndex];
                insertIndex--;
            }

            if (insertIndex + 1 != i) {
                array[insertIndex + 1] = insertValue;
            }
        }
    }

    // 系统排序
    public static void comparator(int... array) {
        Arrays.sort(array);
    }

    // 生成随机数组
    public static int[] generateArray(int maxSize, int maxValue) {
        int[] array = new int[(int) (Math.random() * (maxSize + 1))];
        for (int i = 0; i < array.length - 1; i++) {
            array[i] = (int) (Math.random() * (maxValue + 1));
        }
        return array;
    }


    //数组复制
    public static int[] copyArray(int... array) {
        return array.clone();
    }

    // 数组比对
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        //测试单数组排序
        //int[] arr = {1, 5, 6, 4, 3, 12};
        //insertSort(arr);
        //for (int i : arr) {
        //    System.out.print(i + " ");
        //}

        int testSize = 1000;
        int maxSize = 1000;
        int maxValue = 9999;
        boolean success = true;
        for (int i = 0; i < testSize; i++) {
            int[] array1 = generateArray(maxSize, maxValue);
            int[] array2 = copyArray(array1);
            insertSort(array1);
            comparator(array2);
            boolean b = isEqual(array1, array2);
            if (!b) {
                success = false;
                break;
            }
        }
        System.out.println(success ? "Nice! 成功" : "What a pity! Failed!!!");
    }
}
